ICPC Live Archive/3928 - Ballroom lights/help/gomox.ar-pap-2010-d9b17e5cb110/tpc/needle-haystack/main_alternativo.cpp

   1 #include <vector>
   2 #include <string>
   3 #include <iostream>
   4 #include <cassert>
   5 #include <cstdlib>
   6
   7 using namespace std;
   8
   9 typedef unsigned long long int lluint;
  10 typedef vector<int> vint;
  11 typedef vector<vint> vvint;
  12
  13 #define forsn(i, s, n)  for (int i = (s); i < (n); i++)
  14 #define forn(i, n)      forsn (i, 0, n)
  15
  16 void pkmp(const string& s, vint& f) {
  17         int z = f[0] = -1;
  18         forsn (i, 1, s.size() + 1) {
  19                 while (z != -1 && s[i - 1] != s[z]) z = f[z];
  20                 f[i] = ++z; // z might be -1
  21         }
  22 }
  23
  24 vvint tran;
  25
  26 #define ALPHA_SIZE      128
  27 void build_transitions(const string& s) {
  28         uint n = s.size() + 1;
  29         vint f(n);
  30         tran = vvint(n, vint(ALPHA_SIZE, 0));
  31         pkmp(s, f);
  32         forn (state, n) {
  33                 forn (a, ALPHA_SIZE) {
  34                         int z = state;
  35                         while (z != -1 && s[z] != (char)a) z = f[z];
  36                         tran[state][a] = z + 1;
  37                 }
  38         }
  39 }
  40
  41 // Buffer
  42
  43 #define TAMBUF  65536
  44 lluint pos;
  45 char buf[TAMBUF];
  46 int buf_size;
  47
  48 #define buf_sync() { \
  49         cin.getline(buf, TAMBUF + 1); \
  50         pos += buf_size; \
  51         buf_size = cin.gcount(); \
  52         cin.clear(); \
  53 }
  54
  55 #define buf_start() { \
  56         buf_sync(); \
  57         pos = 0; \
  58 }
  59
  60 void search() {
  61         buf_start();
  62         const int final = tran.size() - 1;
  63         int state = 0;
  64         while (true) {
  65                 forn (i, buf_size) {
  66                         if (state == final) {
  67                                 cout << (pos + i - final) << " ";
  68                         }
  69                         state = tran[state][buf[i]];
  70                 }
  71                 if (buf_size < TAMBUF) break;
  72                 buf_sync();
  73         }
  74 }
  75
  76 int main() {
  77         for (;;) {
  78                 int needle_size;
  79                 string needle;
  80                 cin >> needle_size;
  81                 if (cin.eof()) break;
  82                 cin >> needle;
  83                 assert(needle_size == needle.size());
  84                 cin.ignore(1);
  85
  86                 build_transitions(needle);
  87                 search();
  88
  89                 cout << endl;
  90         }
  91         return 0;
  92 }
  93